/**
 * 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
 *
 * 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
 * 思路：使用位运算
 * 记原序列中元素的总数为 n。原序列中的每个数字 ai的状态可能有两种，即「在子集中」和「不在子集中」。我们用 1 表示「在子集中」，0 表示不在子集中，那么每一个子集可以对应一个长度为 n 的 0/1 序列，第 i 位表示 ai
 是否在子集中。例如，n = 3n,a={5,2,9} 时：

 * 0/1 序列	子集	0/1 序列对应的二进制数
 * 000	      {}	0
 * 001	     {9}	1
 * 01        {2}	2
 * 011	   {2,9}	3
 * 100      {5} 	4
 * 10      {5,9}	5
 * 110	   {5,2}	6
 * 111	  {5,2,9}	7
 * 可以发现 0/1 序列对应的二进制数正好从 0 到 2^n - 1
 。我们可以枚举mask∈[0,2^n−1]，mask 的二进制表示是一个 0/1 序列，我们可以按照这个 0/1 序列在原集合当中取数。当我们枚举完所有 2^n个mask，我们也就能构造出所有的子集。
 *https://leetcode.cn/problems/subsets/solution/zi-ji-by-leetcode-solution/
 */
class SubsetsWeiYunSuan {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ret=new ArrayList<>();
        int n=nums.length;
        int size=1<<n;
        for(int i=0;i<size;i++){
            List<Integer> list=new ArrayList<>();
            for(int j=0;j<n;j++){
                if(((i>>j)&1)==1){
                    list.add(nums[j]);
                }
            }
            ret.add(list);
        }
        return ret;
    }
}